﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Edutainment
{
    [Serializable()]
    public class MergeSort : SortAlgorithm
    {
        public MergeSort()
            : base("MergeSort")
        {
        }

        public MergeSort(int exer, int sExer, int exa, int sExa)
            : base("MergeSort")
        {
            exercises = exer;
            solvedExercises = sExer;
            exams = exa;
            solvedExams = sExa;
        }

        public void createListToSort(int count, bool exam)
        {
            base.createListToSort(count, exam);
            this.sortForCorrectSteps(listToSort);
        }

        private ArrayList[] halveList(ArrayList listToSplit)
        {
            ArrayList[] newHalves = new ArrayList[2];

            int newListLength = (int)Math.Ceiling(listToSplit.Count / 2.0);
            int k = 0, l;

            for (int i = 0; i < newHalves.Length; i++)
            {
                l = k + newListLength;
                newHalves[i] = new ArrayList();
                for (int j = k; j < l; j++)
                {
                    newHalves[i].Add(listToSplit[j]);
                }
                k += newListLength;
                newListLength = listToSplit.Count - newListLength;
            }
            return newHalves;

        }

        private ArrayList merge(ArrayList left, ArrayList right)
        {
            ArrayList mergedList = new ArrayList();
            while (left.Count > 0 && right.Count > 0)
            {
                if ((int)left[0] <= (int)right[0])
                {
                    mergedList.Add(left[0]);
                    left.RemoveAt(0);
                }
                else
                {
                    mergedList.Add(right[0]);
                    right.RemoveAt(0);
                }
            }

            while (left.Count > 0)
            {
                mergedList.Add(left[0]);
                left.RemoveAt(0);
            }

            while (right.Count > 0)
            {
                mergedList.Add(right[0]);
                right.RemoveAt(0);
            }

            return mergedList;
        }

        private ArrayList mergeSort(ArrayList toSort)
        {
            if (toSort.Count <= 1)
            {
                return toSort;
            }
            ArrayList[] halves = halveList(toSort);
            ArrayList leftHalf = halves[0];
            ArrayList rightHalf = halves[1];

            leftHalf = mergeSort(leftHalf);
            rightHalf = mergeSort(rightHalf);

            return merge(leftHalf, rightHalf);
        }

        private void sortForCorrectSteps(ArrayList toSort)
        {
            if (toSort != null)
            {
                ArrayList tempSortList = new ArrayList(toSort);
                tempSortList = mergeSort(tempSortList);
            }
        }
    }
}
